【LeetCode 90】Subsets II 子集II

发表于 | 分类于

【LeetCode 90】Subsets II 子集II

问题描述:

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution:

Solution: 这道问题相对于leetcode78差别在于包含重复元素，所以这道题要解决的就是去重，也就是dfs的时候减枝，考虑序列1，2，2，2，当要回溯到1，2时，遍历下一位判断与上一位是否相同，若相同跳过即可去重，当然这么做的前提条件是原序列是有序的，所以要在原序列做个排序。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public List<List<Integer>> subsetsWithDup (int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        Arrays.sort(nums);
        helper(res, new LinkedList<Integer>(), 0, nums);
        return res;
    }

    private void helper (List<List<Integer>> res, List<Integer> bag, int pos, int[] nums) {
        res.add(new LinkedList<>(bag));
        for (int i = pos; i < nums.length; i++) {
            if (i > pos && nums[i] == nums[i - 1]) continue;
            List<Integer> temp = new LinkedList<>(bag);
            bag.add(nums[i]);
            helper(res, bag, i + 1, nums);
            bag = temp;
        }
    }
}
Thanks!